package commonusealgorithm;

import java.util.Arrays;

/**
 * @Author PoX21s
 * @Date: 2021/11/3 16:37
 * @Version 1.0
 */

public class DijkstraAlgorithm {

    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = new int[vertex.length][vertex.length];

        final int N = 65535;

        matrix[0] = new int[]{N, 5, 7, N, N, N, 2};
        matrix[1] = new int[]{5, N, N, 9, N, N, 3};
        matrix[2] = new int[]{7, N, N, N, 8, N, N};
        matrix[3] = new int[]{N, 9, N, N, N, 4, N};
        matrix[4] = new int[]{N, N, 8, N, N, 5, 4};
        matrix[5] = new int[]{N, N, N, 4, 5, N, 6};
        matrix[6] = new int[]{2, 3, N, N, 4, 6, N};

//        System.out.println(Arrays.toString(djs(matrix, 2)));

        int[][] floyd = Floyd(matrix);

        for (int[] ints : floyd) {
            System.out.println(Arrays.toString(ints));
        }

    }

    /*
     * 思路
     * - 传入路径权值图和开始的点
     * - 创建三个数组
     *   - 当前这个节点是否已经访问过
     *   - 到达这个结点的前驱结点是什么
     *   - 从开始节点到达这个结点所需要的距离为
     * - 将dis进行初始的赋值
     * - 找到开始结点能够达到的最近节点
     *   - 使用广度优先查找，找出这个新找到的结点能够到达最近的结点
     *   - 循环直到达到所有能够到达的节点（通过其他节点中转也能达到的节点）
     * */
    public static int[] djs(int[][] matrix, int start) {
        int[] isVisited = new int[matrix.length];
        int[] preVertex = new int[matrix.length];

        isVisited[start] = 1;

        Arrays.fill(preVertex, start);

        for (int i = 1; i < matrix.length; i++) {
            int min = 65535;
            int next = 0;
            for (int j = 0; j < matrix.length; j++) {
                if (isVisited[j] != 1 && matrix[start][j] < min) {
                    min = matrix[start][j];
                    next = j;
                }
            }

            isVisited[next] = 1;

            for (int j = 0; j < matrix.length; j++) {
                if (j == next || matrix[next][j] > 65534 || isVisited[j] == 1) {
                    continue;
                }
                if (matrix[start][j] > matrix[start][next] + matrix[next][j]) {
                    matrix[start][j] = matrix[start][next] + matrix[next][j];
                    preVertex[j] = next; // j = 1 next = 0
                }
            }
        }
        System.out.println(Arrays.toString(preVertex));
        return matrix[start];
    }

/*
    1.初始设置所有结点的前驱结点为当前结点
2.判断从A结点到其他结点时，如果经中间结点是否会减少距离
   -有则更新距离表和前驱结点表
   -没有则不更新
3.三嵌套循环，遍历每一种情况
*/

    public static int[][] Floyd(int[][] matrix) {
        char[][] pre = new char[matrix.length][matrix.length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (i == 0) {
                    pre[i][j] = 'A';
                }
                if (i == 1) {
                    pre[i][j] = 'B';
                }
                if (i == 2) {
                    pre[i][j] = 'C';
                }
                if (i == 3) {
                    pre[i][j] = 'D';
                }
                if (i == 4) {
                    pre[i][j] = 'E';
                }
                if (i == 5) {
                    pre[i][j] = 'F';
                }
                if (i == 6) {
                    pre[i][j] = 'G';
                }
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                int len = 0;
                for (int k = 0; k < matrix.length; k++) {
                    len = matrix[j][i] + matrix[i][k];
                    if (matrix[j][k] > len) {
                        matrix[j][k] = len;
                        pre[j][k] = pre[i][k];
                    }
                }
            }
        }
        return matrix;
    }
}


        /*GraphDJS graph = new GraphDJS(vertex, matrix);

        graph.showGraph();

       graph.djs(6);

       graph.show();

    }
}

class GraphDJS {
    char[] vertex;
    int[][] matrix;
    VisitedVertex vv;

    public GraphDJS(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    public void showGraph(){
        for (int[] ints : matrix) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public void djs(int index){
        vv = new VisitedVertex(vertex.length,index);
        upDate(index);
        for (int i = 0; i < vertex.length; i++) {
            index = vv.updateArr();
            upDate(index);
        }
    }

    public void upDate(int index){
        int len =0;

        for (int i = 0; i < matrix[index].length; i++) {
            len = vv.getDis(index) + matrix[index][i];
            if (!vv.getIsVisited(i) && len < vv.getDis(i)){
                vv.setDis(i,len);
                vv.setPreVertex(i,index);
            }
        }
    }

    public void show(){
        vv.show();
    }
}

class VisitedVertex{
    private int[] isVisited;
    private int[] preVertex;
    private int[] dis;

    public VisitedVertex(int len,int index) {
        this.isVisited = new int[len];
        this.preVertex = new int[len];
        this.dis = new int[len];
        Arrays.fill(dis,65535);
        dis[index] = 0;
        isVisited[index] = 1;
    }

    public boolean getIsVisited(int index){
        return isVisited[index] == 1;
    }

    public void setPreVertex(int pre, int index){
        preVertex[pre] = index;
    }

    public int getPreVertex(int index){
        return preVertex[index];
    }

    public void setDis(int index , int len){
        dis[index] = len;
    }

    public int getDis(int index){
        return dis[index];
    }

    public int updateArr(){
        int min = 65535,index = 0;
        for (int i = 0; i < isVisited.length; i++) {
            if (isVisited[i] == 0 && dis[i] < min){
                min = dis[i];
                index = i;
            }
        }
        isVisited[index] = 1;
        return index;
    }

    public void show() {
        System.out.println("==========================");

        for(int i : isVisited) {
            System.out.print(i + " ");
        }

        System.out.println();

        //输出 pre_visited
        for(int i : preVertex) {
            System.out.print(i + " ");
        }

        System.out.println();

        //输出 dis
        for(int i : dis) {
            System.out.print(i + " ");
        }

        System.out.println();

        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };

        int count = 0;

        for (int i : dis) {
            if (i != 65535) {
                System.out.print(vertex[count] + "("+i+") ");
            } else {
                System.out.println("N ");
            }
            count++;
        }

        System.out.println();
    }
}*/